package leetcode19

type ListNode struct {
	Val  int
	Next *ListNode
}

// 可以添加头结点简化问题
func removeNthFromEnd(head *ListNode, n int) *ListNode {

	var nodeArr []*ListNode = make([]*ListNode, 0)
	cur := head
	for cur != nil {
		nodeArr = append(nodeArr, cur)
		cur = cur.Next
	}
	if n == len(nodeArr) {
		return head.Next
	}

	if n == 1 {
		nodeArr[len(nodeArr)-1-n].Next = nil
		return head
	}

	// 1, 2, 3, 4, 5
	nodeArr[len(nodeArr)-1-n].Next = nodeArr[len(nodeArr)+1-n]
	return head
}

func removeNthFromEndV1(head *ListNode, n int) *ListNode {
	length := getListLen(head)
	index := length - n
	dummy := &ListNode{0, head}
	cur := dummy
	for index > 0 {
		cur = cur.Next
		index--
	}
	cur.Next = cur.Next.Next
	return dummy.Next
}

func getListLen(head *ListNode) int {
	length := 0
	for head != nil {
		length++
		head = head.Next
	}
	return length
}
